What's a Balanced BST?

	a BST with insert and remove algorithms that keep the tree balanced

What are examples of specific types of Balanced BSTs?

	AVL trees (first balanced BST, we will study)
	Red-Black trees (often used in practice, we will not study)


What's an AVL tree?

	BST with extra balance property
	named after Adelson-Velskii and Landis

What's the AVL Balance Property?

	for any node in the tree
	height of left and right subtrees differ by at most 1

Draw an example AVL tree on the board.

How well does an AVL tree stay balanced?

	worst case height is about 1.44 times best case
	typical case height is close to log N
	find, insert, and remove are O(log n)


How do you find a key in an AVL tree?

	same as in a regular BST

How do you insert a key in an AVL tree?

	insert as in a standard BST
	some nodes can be out of balance
	restore balance using rotations

Show an insertion that violates the AVL property.


How do you know if rebalancing is needed?

	look for nodes that violate the AVL property


Where do you find the unbalanced nodes that need balancing?

	only nodes from root to insert point can be out of balance
	for insert only fix balance at deepest node, fixes whole tree


What are the four possible cases where a node can be out of balance?

	left > right, left-left > left-right
	left > right, left-left < left-right
	right > left, right-right > right-left
	right > left, right-right < right-left


How do you rebalance when the left child is higher and the left-left
grandchild is higher?

	Single Right Rotation
	    left = root.left;
	    root.left = left.right;
	    left.right = root;
	    return left;

Show an example single-right rotation on the board.


How do you rebalance when the right child is higher and the
right-right grandchild is higher?

	Single Left Rotation
	    right = root.right;
	    root.right = right.left;
	    right.left = root;
	    return right;

Show an example single-left rotation on the board.


What happens if you try to do a single right rotation when the left
child is higher and the left-right grandchild is higher?

	single rotate doesn't work
	tree is still unbalanced

Show an example of a failed single rotate.


How can you correct this type of imbalance?

	solve with 2 single rotations
	double rotation


How do you rebalance when the left child is higher and the left-right
grandchild is higher?

	Double Right Rotation
	    root.left = rotateLeft(root.left);
	    root = rotateRight(root);

Show an example double right rotation on the board.


How do you rebalance when the right child is higher and the
right-left grandchild is higher?

	Double Left Rotation
	    root.right = rotateRight(root.right);
	    root = rotateLeft(root);

Show an example double left rotation on the board.


Show the insertion of values 1 to 10 into an AVL tree on the board.

Show the removal of several values from an AVL tree on the board.


Classwork
You may work with a partner.
Show the result of inserting C, A, D, F, E, B into an initially empty AVL tree.
Show the result of removing C, E, D from the previous tree.